//
// Created by Administrator on 2021/8/3.
//
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>

using namespace std;

class Solution {
public:
    /**
     * 贪心  给一个小朋友能满足胃口的最小的糖果
     * @param g
     * @param s
     * @return
     */
    int findContentChildren(vector<int> &g, vector<int> &s) {
        if (g.empty() or s.empty())
            return 0;
        sort(g.rbegin(), g.rend());
        sort(s.rbegin(), s.rend());
        int i = 0; // 指针
        int ans = 0;
        for (auto &x:g) {
            if (x <= s[i]) {
                ++i; // 糖果可以满足这个小朋友  移动指针
                ++ans;
            }
            if (i >= s.size())
                break;
        }
        return ans;
    }
};

class Solution2 {
public:
    int findContentChildren(vector<int> &g, vector<int> &s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        auto numOfChildren = g.size(), numOfCookies = s.size();
        int count = 0;
        for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
            // 从小到大遍历
            while (j < numOfCookies && g[i] > s[j]) {
                // 这颗糖果不够 试下一颗
                j++;
            }
            if (j < numOfCookies) {
                count++;
            }
        }
        return count;
    }
};


int main() {
    vector<int> children{1, 2, 2, 1};
    vector<int> biscuits{1, 3, 5};
    Solution2 solution;
    cout << solution.findContentChildren(children, biscuits) << endl;
    return 0;
}
